1. Field of the Invention
The present invention relates to prime and composite number computing and applications of the same, e.g., in the area of data security.
2. State of the Art
Prime numbers (2, 3, 5, 7, 11, 13, . . . , those positive integers divisible only by themselves or 1) are the most fundamental building blocks of math, and with the invention of the public key ciphers (RSA, El Gamal and the like), they now form the backbone of computer security. Basically there are two problems related to the use of prime numbers in these fields, namely primality testing and factoring. The primality testing problem is about testing and determining whether a given arbitrary positive integer is a prime number or a composite (non-prime) number. For a composite number, the factoring problem requires determining the composite number's prime factors. Practicality demands that these two problems have to be solved in polynomial time (computations being proportional to the number of digits and therefore fast), not exponential time (computations being proportional to the size of the numbers themselves and therefore too slow).
Traditionally, to decide whether a small integer is prime or composite, one can try to factor it with the smaller primes, but this trial division is too tedious for numbers greater than, say, 40 digits. Previously, experts have only been able to test for general primality up to about 2000 digits with certainty in a week of standard PC computational time. Several other faster methods have been devised to test larger integers, but they too fall short of expectations.
Presently over the Internet, record-size prime numbers over 10,000 or 100,000 digits are frequently found and published by researchers, but they are confined to special forms only (e.g., the most famous being the Lucas-Lehmer test for Mersenne numbers of the form 2M−1). If given an arbitrary number, however, these researchers cannot test it in polynomial time. The stringent demands of several important ciphers require testing and generating large prime number of arbitrary forms and sizes.
There are four conditions in solving these problems:                1. Polynomial-time algorithm: the algorithm's speed needs to be proportional to a small power of the number of digits of that integer, e.g. d3, instead of sub-exponential or exponential time, e.g., 2d.        2. 100% generality, i.e., the primality or factors of any arbitrary number can be determined.        3. Provability, i.e., it can be shown to work in all cases mathematically and no counterexamples can be found.        4. Deterministic in nature, i.e., the algorithm can determine the primality of a number with certainty and not with statistical probability.        
Present techniques are unable to satisfy all four of these conditions simultaneously.